Crate scc

Scalable Concurrent Containers

A collection of high performance containers and utilities for concurrent and asynchronous programming.

Features

• Asynchronous counterparts to blocking and synchronous methods.
• Formally verified EBR implementation.
• Near-linear scalability.
• No spin-locks and no busy loops.
• Zero dependencies on other crates.
• Serde support: features = ["serde"].

Concurrent and Asynchronous Containers

• HashMap is a concurrent and asynchronous hash map.
• HashSet is a concurrent and asynchronous hash set.
• HashIndex is a read-optimized concurrent and asynchronous hash map.
• HashCache is a sampling-based LRU cache backed by HashMap.
• TreeIndex is a read-optimized concurrent and asynchronous B-plus tree.

Utilities for Concurrent Programming

• EBR implements lock-free epoch-based reclamation.
• LinkedList is a type trait implementing a lock-free concurrent singly linked list.
• Queue is a concurrent lock-free first-in-first-out container.
• Stack is a concurrent lock-free last-in-first-out container.
• Bag is a concurrent lock-free unordered opaque container.

HashMap

HashMap is a concurrent hash map that is targeted at highly concurrent write-heavy workloads. HashMap is basically an array of entry buckets where each bucket is protected by a special read-write lock providing both blocking and asynchronous methods. The bucket array is fully managed by EBR enabling lock-free access to it and non-blocking array resizing.

Locking behavior

Entry access: fine-grained locking

Read/write access to an entry is serialized by the read-write lock in the bucket containing the entry. There are no container-level locks, therefore, the larger the container gets, the lower the chance of the bucket-level lock being contended.

Resize: lock-free

Resizing of the container is totally non-blocking and lock-free; resizing does not block any other read/write access to the container or resizing attempts. Resizing is analogous to pushing a new bucket array into a lock-free stack. Each individual entry in the old bucket array will be incrementally relocated to the new bucket array on future access to the container, and the old bucket array gets dropped eventually when it becomes empty.

Examples

An entry can be inserted if the key is unique. The inserted entry can be updated, read, and removed synchronously or asynchronously.

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();

assert!(hashmap.insert(1, 0).is_ok());
assert_eq!(hashmap.update(&1, |_, v| { *v = 2; *v }).unwrap(), 2);
assert_eq!(hashmap.read(&1, |_, v| *v).unwrap(), 2);
assert_eq!(hashmap.remove(&1).unwrap(), (1, 2));

hashmap.entry(7).or_insert(17);
assert_eq!(hashmap.read(&7, |_, v| *v).unwrap(), 17);

let future_insert = hashmap.insert_async(2, 1);
let future_remove = hashmap.remove_async(&1);

upsert will insert a new entry if the key does not exist, otherwise update the value field.

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();

hashmap.upsert(1, || 2, |_, v| *v = 2);
assert_eq!(hashmap.read(&1, |_, v| *v).unwrap(), 2);
hashmap.upsert(1, || 2, |_, v| *v = 3);
assert_eq!(hashmap.read(&1, |_, v| *v).unwrap(), 3);

let future_upsert = hashmap.upsert_async(2, || 1, |_, v| *v = 3);

HashMap does not provide an Iterator since it is impossible to confine the lifetime of Iterator::Item to the Iterator. The limitation can be circumvented by relying on interior mutability, e.g., let the returned reference hold a lock, however it will easily lead to a deadlock if not correctly used, and frequent acquisition of locks may impact performance. Therefore, Iterator is not implemented, instead, HashMap provides a number of methods to iterate over entries synchronously or asynchronously: any, any_async, for_each, for_each_async, OccupiedEntry::next, OccupiedEntry::next_async, prune, prune_async, retain, retain_async, scan, and scan_async.

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();

assert!(hashmap.insert(1, 0).is_ok());
assert!(hashmap.insert(2, 1).is_ok());

// `for_each` allows entry modification.
let mut acc = 0;
hashmap.for_each(|k, v_mut| { acc += *k; *v_mut = 2; });
assert_eq!(acc, 3);
assert_eq!(hashmap.read(&1, |_, v| *v).unwrap(), 2);
assert_eq!(hashmap.read(&2, |_, v| *v).unwrap(), 2);

// `any` returns `true` as soon as an entry satisfying the predicate is found.
assert!(hashmap.insert(3, 2).is_ok());
assert!(hashmap.any(|k, _| *k == 3));

// `retain` enables entry removal.
assert_eq!(hashmap.retain(|k, v| *k == 1 && *v == 2), (1, 2));

// `hash_map::OccupiedEntry` also can return the next closest occupied entry.
let first_entry = hashmap.first_occupied_entry();
assert!(first_entry.is_some());
let second_entry = first_entry.and_then(|e| e.next());
assert!(second_entry.is_none());

// Asynchronous iteration over entries using `scan_async` and `for_each_async`.
let future_scan = hashmap.scan_async(|k, v| println!("{k} {v}"));
let future_for_each = hashmap.for_each_async(|_, v_mut| { *v_mut = 0; });

HashSet

HashSet is a special version of HashMap where the value type is ().

Examples

Most HashSet methods are identical to that of HashMap except that they do not receive a value argument, and some HashMap methods for value modification are not implemented for HashSet.

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::default();

assert!(hashset.read(&1, |_| true).is_none());
assert!(hashset.insert(1).is_ok());
assert!(hashset.read(&1, |_| true).unwrap());

let future_insert = hashset.insert_async(2);
let future_remove = hashset.remove_async(&1);

HashIndex

HashIndex is a read-optimized version of HashMap. In a HashIndex, not only is the memory of the bucket array managed by EBR, but also that of entry buckets is protected by EBR, enabling lock-free read access to individual entries.

Examples

The read method is completely lock-free.

use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();

assert!(hashindex.insert(1, 0).is_ok());
assert_eq!(hashindex.read(&1, |_, v| *v).unwrap(), 0);

let future_insert = hashindex.insert_async(2, 1);
let future_remove = hashindex.remove_if_async(&1, |_| true);

An Iterator is implemented for HashIndex, because any derived references can survive as long as the associated ebr::Barrier lives.

use scc::ebr::Barrier;
use scc::hash_index::ModifyAction;
use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();

assert!(hashindex.insert(1, 0).is_ok());

// Existing values can be replaced with new ones.
assert!(hashindex.modify(
    &1,
    |_, v| if *v == 0 { ModifyAction::Update(1) } else { ModifyAction::Remove }));

let barrier = Barrier::new();

// An `ebr::Barrier` has to be supplied to `iter`.
let mut iter = hashindex.iter(&barrier);

// The derived reference can live as long as `barrier`.
let entry_ref = iter.next().unwrap();
assert_eq!(iter.next(), None);

drop(hashindex);

// The entry can be read after `hashindex` is dropped.
assert_eq!(entry_ref, (&1, &1));

HashCache

HashCache is a concurrent sampling-based LRU cache that is based on the HashMap implementation. HashCache does not keep track of the least recently used entry in the entire cache, instead each bucket maintains a doubly linked list of occupied entries which is updated on access to entries in order to keep track of the least recently used entry within the bucket.

Examples

The LRU entry in a bucket is evicted when a new entry is being inserted and the bucket is full.

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::with_capacity(100, 2000);

/// The capacity cannot exceed the maximum capacity.
assert_eq!(hashcache.capacity_range(), 128..=2048);

/// If the bucket corresponding to `1` or `2` is full, the LRU entry will be evicted.
assert!(hashcache.put(1, 0).is_ok());
assert!(hashcache.put(2, 0).is_ok());

/// `1` becomes the most recently accessed entry in the bucket.
assert!(hashcache.get(&1).is_some());

/// An entry can be normally removed.
assert_eq!(hashcache.remove(&2).unwrap(), (2, 0));

TreeIndex

TreeIndex is a B-plus tree variant optimized for read operations. EBR protects the memory used by individual entries, thus enabling lock-free read access to them.

Locking behavior

Read access is always lock-free and non-blocking. Write access to an entry is also lock-free and non-blocking as long as no structural changes are required. However, when nodes are being split or merged by a write operation, other write operations on keys in the affected range are blocked.

Examples

An entry can be inserted if the key is unique, and it can be read, and removed afterwards. Locks are acquired or awaited only when internal nodes are split or merged.

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

assert!(treeindex.insert(1, 2).is_ok());

// `read` is lock-free.
assert_eq!(treeindex.read(&1, |_, v| *v).unwrap(), 2);
assert!(treeindex.remove(&1));

let future_insert = treeindex.insert_async(2, 3);
let future_remove = treeindex.remove_if_async(&1, |v| *v == 2);

Entries can be scanned without acquiring any locks.

use scc::ebr::Barrier;
use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

assert!(treeindex.insert(1, 10).is_ok());
assert!(treeindex.insert(2, 11).is_ok());
assert!(treeindex.insert(3, 13).is_ok());

let barrier = Barrier::new();

// `visitor` iterates over entries without acquiring a lock.
let mut visitor = treeindex.iter(&barrier);
assert_eq!(visitor.next().unwrap(), (&1, &10));
assert_eq!(visitor.next().unwrap(), (&2, &11));
assert_eq!(visitor.next().unwrap(), (&3, &13));
assert!(visitor.next().is_none());

A specific range of keys can be scanned.

use scc::ebr::Barrier;
use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

for i in 0..10 {
    assert!(treeindex.insert(i, 10).is_ok());
}

let barrier = Barrier::new();

assert_eq!(treeindex.range(1..1, &barrier).count(), 0);
assert_eq!(treeindex.range(4..8, &barrier).count(), 4);
assert_eq!(treeindex.range(4..=8, &barrier).count(), 5);

Bag

Bag is a concurrent lock-free unordered container. Bag is completely opaque, disallowing access to contained instances until they are popped. Bag is especially efficient if the number of contained instances can be maintained under ARRAY_LEN (default: usize::BITS / 2)

Examples

use scc::Bag;

let bag: Bag<usize> = Bag::default();

bag.push(1);
assert!(!bag.is_empty());
assert_eq!(bag.pop(), Some(1));
assert!(bag.is_empty());

Queue

Queue is an EBR backed concurrent lock-free first-in-first-out container.

Examples

use scc::Queue;

let queue: Queue<usize> = Queue::default();

queue.push(1);
assert!(queue.push_if(2, |e| e.map_or(false, |x| **x == 1)).is_ok());
assert!(queue.push_if(3, |e| e.map_or(false, |x| **x == 1)).is_err());
assert_eq!(queue.pop().map(|e| **e), Some(1));
assert_eq!(queue.pop().map(|e| **e), Some(2));
assert!(queue.pop().is_none());

Stack

Stack is an EBR backed concurrent lock-free last-in-first-out container.

Examples

use scc::Stack;

let stack: Stack<usize> = Stack::default();

stack.push(1);
stack.push(2);
assert_eq!(stack.pop().map(|e| **e), Some(2));
assert_eq!(stack.pop().map(|e| **e), Some(1));
assert!(stack.pop().is_none());

EBR

The ebr module implements epoch-based reclamation and various types of auxiliary data structures to make use of it safely. Its epoch-based reclamation algorithm is similar to that implemented in crossbeam_epoch, however users may find it easier to use as the lifetime of an instance is safely managed. For instance, ebr::AtomicArc and ebr::Arc hold a strong reference to the underlying instance, and the instance is automatically passed to the garbage collector when the reference count drops to zero.

Memory Overhead

Retired instances are stored in intrusive queues in thread-local storage, and therefore each instance must provide 16-byte space for the intrusive queue data structure to access Option<NonNull<dyn Collectible>>.

Examples

The ebr module can be used without an unsafe block.

use scc::ebr::{suspend, Arc, AtomicArc, AtomicOwned, Barrier, Ptr, Tag};

use std::sync::atomic::Ordering::Relaxed;

// `atomic_arc` holds a strong reference to `17`.
let atomic_arc: AtomicArc<usize> = AtomicArc::new(17);

// `atomic_owned` owns `19`.
let atomic_owned: AtomicOwned<usize> = AtomicOwned::new(19);

// `barrier` prevents the garbage collector from dropping reachable instances.
let barrier: Barrier = Barrier::new();

// `ptr` cannot outlive `barrier`.
let mut ptr: Ptr<usize> = atomic_arc.load(Relaxed, &barrier);
assert_eq!(*ptr.as_ref().unwrap(), 17);

// `atomic_arc` can be tagged.
atomic_arc.update_tag_if(Tag::First, |p| p.tag() == Tag::None, Relaxed, Relaxed);

// `ptr` is not tagged, so CAS fails.
assert!(atomic_arc.compare_exchange(
    ptr,
    (Some(Arc::new(18)), Tag::First),
    Relaxed,
    Relaxed,
    &barrier).is_err());

// `ptr` can be tagged.
ptr.set_tag(Tag::First);

// The return value of CAS is a handle to the instance that `atomic_arc` previously owned.
let prev: Arc<usize> = atomic_arc.compare_exchange(
    ptr,
    (Some(Arc::new(18)), Tag::Second),
    Relaxed,
    Relaxed,
    &barrier).unwrap().0.unwrap();
assert_eq!(*prev, 17);

// `17` will be garbage-collected later.
drop(prev);

// `ebr::AtomicArc` can be converted into `ebr::Arc`.
let arc: Arc<usize> = atomic_arc.try_into_arc(Relaxed).unwrap();
assert_eq!(*arc, 18);

// `18` and `19` will be garbage-collected later.
drop(arc);
drop(atomic_owned);

// `17` is still valid as `barrier` keeps the garbage collector from dropping it.
assert_eq!(*ptr.as_ref().unwrap(), 17);

// Execution of a closure can be deferred until all the current readers are gone.
barrier.defer_execute(|| println!("deferred"));
drop(barrier);

// If the thread is expected to lie dormant for a while, call `suspend()` to allow other threads
// to reclaim its own retired instances.
suspend();

LinkedList

LinkedList is a type trait that implements lock-free concurrent singly linked list operations, backed by EBR. It additionally provides a method for marking an entry of a linked list to denote a user-defined state.

Examples

use scc::ebr::{Arc, AtomicArc, Barrier};
use scc::LinkedList;

use std::sync::atomic::Ordering::Relaxed;

#[derive(Default)]
struct L(AtomicArc<L>, usize);
impl LinkedList for L {
    fn link_ref(&self) -> &AtomicArc<L> {
        &self.0
    }
}

let barrier = Barrier::new();

let head: L = L::default();
let tail: Arc<L> = Arc::new(L(AtomicArc::null(), 1));

// A new entry is pushed.
assert!(head.push_back(tail.clone(), false, Relaxed, &barrier).is_ok());
assert!(!head.is_marked(Relaxed));

// Users can mark a flag on an entry.
head.mark(Relaxed);
assert!(head.is_marked(Relaxed));

// `next_ptr` traverses the linked list.
let next_ptr = head.next_ptr(Relaxed, &barrier);
assert_eq!(next_ptr.as_ref().unwrap().1, 1);

// Once `tail` is deleted, it becomes invisible.
tail.delete_self(Relaxed);
assert!(head.next_ptr(Relaxed, &barrier).is_null());

Performance

HashMap and HashIndex

Comparison with DashMap.

• Results on Apple M1 (8 cores).
• Results on Intel Xeon (VM, 40 cores).
• Interpret the results cautiously as benchmarks usually do not represent real world workloads.

EBR

• The average time taken to enter and exit a protected region: 2.1 nanoseconds on Apple M1.

Changelog

Re-exports

• pub use hash_map::HashMap;
• pub use hash_set::HashSet;
• pub use hash_index::HashIndex;
• pub use hash_cache::HashCache;
• pub use tree_index::TreeIndex;

Modules

• ebr
  Epoch-based reclamation.
• hash_cache
  HashCache is a concurrent and asynchronous sampling-based LRU cache backed by HashMap.
• hash_index
  HashIndex is a read-optimized concurrent and asynchronous hash map.
• hash_map
  HashMap is a concurrent and asynchronous hash map.
• hash_set
  HashSet is a concurrent and asynchronous hash set.
• tree_index
  TreeIndex is a read-optimized concurrent and asynchronous B-plus tree.

Structs

• Bag
  Bag is a lock-free concurrent unordered instance container.
• LinkedEntry
  Entry stores an instance of T and a link to the next entry.
• Queue
  Queue is a lock-free concurrent first-in-first-out container.
• Stack
  Stack is a lock-free concurrent last-in-first-out container.

Traits

• LinkedList
  LinkedList is a type trait implementing a lock-free singly linked list.